МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ВИВЧЕННЯ ТА ДОСЛІДЖЕННЯ АЛГОРИТМІВ ШИФРУВАННЯ РЮКЗАКА.
МЕТОДИЧНІ ВКАЗІВКИ ДО ЛАБОРАТОРНОЇ РОБОТИ № 4
З ДИСЦИПЛІНИ “КРИПТОГРАФІЧНІ СИСТЕМИ ТА ПРОТОКОЛИ”
для студентів базового напряму
6.170101 “Безпека інформаційних і комунікаційних систем”
Затверджено на засiданнi кафедри
“Безпека інформаційних технологій”,
протокол № від 2012 р.
Львів – 2012
Вивчення та дослідження алгоритмів шифрування рюкзака: Методичні вказівки до лабораторної роботи №4 з дисципліни “Криптографічні системи та протоколи” для студентів базового напряму 6.170101 “Безпека інформаційних і комунікаційних систем” /Укл.: А.Е.Лагун, А.В.Петришин - Львів: НУЛП 2012. - 8 с.
Укладачі:
А.Е.Лагун, к.т.н., доцент
А.В.Петришин, асистент
Відповідальний за випуск:
Л.В. Мороз, к.т.н., доцент.
Рецензент:
В.М.Максимович, д.т.н., професор.
Мета роботи – навчитися практично використовувати алгоритми шифрування рюкзака і розробляти програмне забезпечення для реалізації цих алгоритмів.
1. ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Концепція криптографії з відкритими ключами була висунута Уітфілдом Діффі, Мартіном Хелманом, і незалежно Ральфом Мерклом. Їхня ідея полягала в тому, що ключі можна використовувати парами – ключ шифрування та ключ розшифрування – і що можна одержати один ключ з іншого.
Не всі криптографічні алгоритми з відкритим ключем є безпечними і практичними. Одні з безпечних та практичних алгоритмів можуть бути використані лише для розподілу ключів. Другі використовуються для шифрування. Треті можуть використовуватися лише для цифрових підписів. Проте всі ці алгоритми є повільними, оскільки шифрують та розшифровують значно повільніше, ніж симетричні алгоритми.
Гібридні криптосистеми дозволяють прискорити процес: для шифрування повідомлення використовується симетричний алгоритм із випадковим ключем, а алгоритм з відкритим ключем використовується для шифрування випадкового сеансового ключа.
Безпека алгоритмів з відкритими ключами.
Оскільки у криптоаналітика є доступ до відкритого ключа, він завжди може вибрати для шифрування довільне повідомлення. Це означає, що криптоаналітик для заданого C=Ek(P) може спробувати вгадати значення P і легко перевірити свій здогад. Це є проблемою, якщо кількість можливих відкритих текстів є дуже малою, що дозволяє зробити вичерпний пошук. Проте ця проблема вирішується за рахунок доповнення повідомлення рядком випадкових бітів.
Це особливо важливо, якщо алгоритм з відкритим ключем використовується для шифрування сеансового ключа. Алгоритми з відкритими ключами спроектовані таким чином, щоб запобігати викриванню з вибраним відкритим текстом. Їхня безпека полягає як на складності одержання секретного ключа з відкритого, так і на складності одержання відкритого тексту за шифротекстом.
В системах, в яких операція, обернена до шифрування, використовується для цифрового підпису, цьому викриванню неможливо запобігти, якщо для шифрування підписів використовувати однакові ключі.
Алгоритми рюкзака.
Безпека алгоритму рюкзака полягає в проблемі рюкзака, NP-повну проблему.
Дано багато предметів різної маси. Необхідно поскладати деякі з цих предметів в рюкзак так, щоб маса рюкзака дорівнювала певному значенню.
У формалізованому вигляді задача виглядає так: дано набір значень M1, M2, … , Mn і сума S; обчислити значення bi такі, що
S=b1M1+b2M2+…+bnMn (1)
де bi може бути або нулем , або одиницею; одиниця означає, що предмет складають в рюкзак, а нуль – що не складають.
Наприклад маси предметів можуть бути 1, 5, 6, 11, 14, 20. Можна запакувати рюкзак так, щоб його маса була 22, використавши маси 5, 6 і 11. Проте неможливио одержати результуючу масу 24. Час, необхідний для вирішення цієї проблеми із збільшенням кількості предметів зростає експонентно.
Ідеєю алгоритму Меркла-Хелмана є шифрування повідомлення як розв’язку набору проблем рюкзака. Предмети вибираються за допомогою блоку відкритого тексту, який за довжи...
